package graph.undirectedgraph.mgraph;

import graph.inter.UndirectedGraph;
import graph.undirectedgraph.Edge;
import stackandqueue.queue.inter.Queue;
import stackandqueue.queue.linkedqueue.LinkedQueue;

import java.util.Scanner;

/**
 * 无向图 - 邻接矩阵
 */
public class MatrixGraph implements UndirectedGraph {
    // 顶点表
    private String[] vexs;
    // 邻接矩阵，可看作边表
    private int[][] arc;
    // 顶点数
    private int numVertexes;
    // 边数
    private int numEdges;
    // 访问标志数组
    private boolean[] visited;

    private Scanner sc;

    public MatrixGraph() {
        this.sc = new Scanner(System.in);
    }

    public MatrixGraph(String[] vexs, int[][] arc) {
        visited = new boolean[vexs.length];
        numEdges = 0;
        if (vexs.length != arc.length) {
            System.out.println("创建失败");
            return;
        }
        for (int[] ints : arc) {
            if (vexs.length != ints.length) {
                System.out.println("创建失败");
                return;
            }
        }
        this.setVexs(vexs);
        this.setArc(arc);
        numVertexes = vexs.length;
        for (int i = 0; i < arc.length; i++) {
            for (int j = i; j < arc[i].length; j++) {
                if (arc[i][j] > 0 && arc[i][j] < MA) {
                    numEdges++;
                }
            }
        }
    }

    @Override
    public void createGraph() {
        System.out.println("输入图的顶点数：");
        numVertexes = sc.nextInt();
        vexs = new String[numVertexes];
        visited = new boolean[numVertexes];
        System.out.println("输入图的边数");
        numEdges = sc.nextInt();
        arc = new int[numVertexes][numVertexes];
        System.out.println("输入图的顶点：");
        for (int i = 0; i < numVertexes; i++) {
            vexs[i] = sc.next();
        }
        for (int i = 0; i < numVertexes; i++) {
            System.out.print(i + "." + vexs[i] + "      ");
        }
        System.out.println();
        for (int k = 0; k < numEdges; k++) {
            System.out.println("输入边（vi,vj）上的下标i,下标j和权w:");
            int i = sc.nextInt();
            int j = sc.nextInt();
            int w = sc.nextInt();
            this.arc[i][j] = w;
            this.arc[j][i] = w;
        }
    }

    @Override
    public int locateVex(String u) {
        for (int i = 0; i < vexs.length; i++) {
            if (vexs[i].equals(u)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public String getVex(int v) {
        if (v < 0 || v >= vexs.length) {
            return null;
        }
        return vexs[v];
    }

    @Override
    public void putVex(int v, String value) {
        if (v < 0 || v >= vexs.length) {
            return;
        }
        vexs[v] = value;
    }

    @Override
    public String firstAdjVex(int v) {
        if (v < 0 || v >= vexs.length) {
            return null;
        }
        for (int i = 0; i < arc[v].length; i++) {
            if (arc[v][i] != 0) {
                return vexs[i];
            }
        }
        return null;
    }

    @Override
    public String nextAdjVex(int v, int w) {
        if (v < 0 || v >= vexs.length
                || w < 0 || w >= vexs.length) {
            return null;
        }
        for (int i = w; i < arc[v].length; i++) {
            if (arc[v][i] != 0) {
                return vexs[i];
            }
        }
        return null;
    }

    @Override
    public void insertVex(String v) {
        String[] vexsTemp = new String[vexs.length + 1];
        int[][] arcTemp = new int[vexs.length + 1][vexs.length + 1];
        for (int i = 0; i < vexs.length; i++) {
            vexsTemp[i] = vexs[i];
        }
        vexs = vexsTemp;
        vexs[vexs.length - 1] = v;
        for (int i = 0; i < arc.length; i++) {
            for (int j = 0; j < arc[i].length; j++) {
                arcTemp[i][j] = arcTemp[i][j];
            }
        }
        arc = arcTemp;
    }

    @Override
    public void deleteVex(String v) {
        int[][] arcTemp = new int[arc.length - 1][arc.length - 1];
        int x = 0;
        int y = 0;
        for (int i = 0; i < arc.length; i++) {
            if (vexs[i].equals(v)) {
                continue;
            }
            for (int j = 0; j < arc[i].length; j++) {
                if (vexs[j].equals(v)) {
                    continue;
                }
                arcTemp[x][y++] = arc[i][j];
            }
            x++;
            y = 0;
        }
        String[] vexsTemp = new String[vexs.length - 1];
        int j = 0;
        for (int i = 0; i < vexs.length; i++) {
            if (!vexs[i].equals(v)) {
                vexsTemp[j++] = vexs[i];
            }
        }
        vexs = vexsTemp;

    }

    @Override
    public void insertArc(int v, int w) {
        if (v < 0 || v >= vexs.length
                || w < 0 || w >= vexs.length) {
            return;
        }
        arc[v][w] = 1;
        arc[w][v] = 1;
    }

    @Override
    public void deleteArc(int v, int w) {
        if (v < 0 || v >= vexs.length
                || w < 0 || w >= vexs.length) {
            return;
        }
        arc[v][w] = 0;
        arc[w][v] = 0;
    }

    @Override
    public void dfsTraverse(int v) {
        if (v < 0 || v >= vexs.length) {
            return;
        }

        for (int i = 0; i < arc.length; i++) {
            visited[i] = false;
        }

        depthFirstSearch(v);
    }

    @Override
    public void bfsTraverse(int v) {
        if (v < 0 || v >= vexs.length) {
            return;
        }
        for (int i = 0; i < arc.length; i++) {
            visited[i] = false;
        }
        Queue<Integer> queue = new LinkedQueue<>();
        queue.enQueue(v);
        while (!queue.queueEmpty()) {
            int temp = queue.deQueue();

            if (!visited[temp]) {
                for (int i = 0; i < arc[temp].length; i++) {
                    if (arc[temp][i] != 0 && !visited[i]) {
                        queue.enQueue(i);
                    }
                }
                visited[temp] = true;
                System.out.print(vexs[temp] + " ");
            }
        }
    }

    /**
     * 深度优先遍历算法
     *
     * @param v 开始遍历的节点
     */
    private void depthFirstSearch(int v) {
        if (v < 0 || v >= vexs.length) {
            return;
        }
        System.out.print(vexs[v] + " ");
        visited[v] = true;
        for (int i = 0; i < arc[v].length; i++) {
            if (arc[v][i] > 0 && arc[v][i] > Integer.MAX_VALUE && !visited[i]) {
                depthFirstSearch(i);
            }
        }
    }

    @Override
    public void miniSpanTreePrim() {
        int min;
        int k;
        int[] adjvex = new int[vexs.length]; // 保存相关顶点下标
        int[] lowcost = new int[vexs.length]; // 保存相关顶点间边的权值
        lowcost[0] = 0; // 初始化第一个权值为0，即将v0加入生成树
        adjvex[0] = 0; // 初始化第一个顶点下标为0
        for (int i = 1; i < vexs.length; i++) {
            lowcost[i] = this.arc[0][i]; // 记录0到各个点的权值
            adjvex[i] = 0; // 将adjvex各个顶点的路径都初始化为0
        }

        for (int i = 1; i < vexs.length; i++) {
            min = MA;
            k = 0;
            for (int j = 0; j < vexs.length; j++) { // 找到与 已记入生成树中的顶点 的距离(权值)最小的顶点
                if (lowcost[j] != 0 && lowcost[j] < min) {
                    min = lowcost[j];
                    k = j;
                }
            }
            System.out.println(adjvex[k] + "-->" + k); // adjvex[k]和k是路径连接的两个顶点
            lowcost[k] = 0; // 将顶点的权值设置为0，表示已经记为生成树的顶点
            for (int p = 0; p < vexs.length; p++) { // 寻找下一个可以记入生成树的顶点
                // lowcost是已记入生成树的顶点到其他顶点的最小权值，arc[k]是k顶点到其他顶点的权值
                if (lowcost[p] != 0 && arc[k][p] < lowcost[p]) {
                    lowcost[p] = arc[k][p]; // 如果k点到p点的距离比已经计入生成树的顶点的距离(权值)小，则用k到p的权值替换原来的权值
                    adjvex[p] = k; // 同时记录p --> k 这条路径
                }
            }
        }
    }

    @Override
    public void miniSpanTreeKruskal() {
        // 获取边集数组并升序排序
        Edge[] edges = getEdges();
        sortEdges(edges);
        // 记录以计入生成树的顶点， 初始化每个值为0
        int[] parent = new int[numVertexes];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = 0;
        }

        // 遍历边集数组
        for (int i = 0; i < edges.length; i++) {
            int m = find(parent, edges[i].getBegin());
            int n = find(parent, edges[i].getEnd());
            if (m != n) {
                parent[m] = n;
                System.out.println(edges[i].getBegin() + "-->" + edges[i].getEnd());
            }
        }
    }

    @Override
    public void shortestPathDijstra(int start, int[] path, int[] dist) {
        int k = 0;
        int min;
        boolean[] finalPath = new boolean[numVertexes]; // findPath[w]表示顶点start到顶点w的最短路径
        dist = new int[numVertexes]; // 记录start到各个顶点的权值
        path = new int[numVertexes]; // 记录路径
        int[][] everyPath = new int[numVertexes][numVertexes]; // 记录到每个点的最短路径
        for (int i = 0; i < numVertexes; i++) {
            finalPath[i] = false;
            dist[i] = arc[start][i];
            path[i] = MA;
        }
        dist[start] = 0; // start到start点路径权值为0
        finalPath[start] = true; // start到start点不需要求路径
        path[start] = 0;

        for (int v = 1; v < numVertexes; v++) {
            min = MA;
            for (int w = 0; w < numVertexes; w++) { // 寻找离start最近的顶点
                if (!finalPath[w] && dist[w] < min) {
                    k = w;
                    min = dist[w]; // i顶点离start更近
                }
            }
            finalPath[k] = true; // 将目前找到的最近的顶点置为true

            for (int i = 0; i < everyPath[k].length; i++) {
                everyPath[k][i] = path[i];
            }
            for (int w = 0; w < numVertexes; w++) {
                if (!finalPath[w] && arc[k][w] < MA && (min + arc[k][w] < dist[w])) {
                    // 说明找到了更短的路径，修改weight[i]和path[i]
                    dist[w] = min + arc[k][w]; // 修改当前路径长度
                    path[w] = k;
                }
            }
        }

        for (int i = 0; i < vexs.length; i++) {
            System.out.println("  shortest(" + vexs[start] + ", " + vexs[i] + ")=" + dist[i]);
        }
//        int prev = everyPath[8][8];
//        System.out.print(vexs[8]);
//        while (prev > 0 && prev < MA) {
//            System.out.print("<--" + vexs[prev]);
//            prev = everyPath[8][prev];
//        }
//        System.out.print("<--" + vexs[start]);
        System.out.println();

    }

    /**
     * Dijkstra最短路径。
     * 即，统计图中"顶点vs"到其它各个顶点的最短路径。
     * <p>
     * 参数说明：
     * vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
     * prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
     * dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
     */
    public void dijkstra(int vs, int[] prev, int[] dist) {
        // flag[i]=true表示"顶点vs"到"顶点i"的最短路径已成功获取
        boolean[] flag = new boolean[vexs.length];

        // 初始化
        for (int i = 0; i < vexs.length; i++) {
            flag[i] = false;          // 顶点i的最短路径还没获取到。
            prev[i] = 0;              // 顶点i的前驱顶点为0。
            dist[i] = arc[vs][i];  // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
        }

        // 对"顶点vs"自身进行初始化
        flag[vs] = true;
        dist[vs] = 0;

        // 遍历mVexs.length-1次；每次找出一个顶点的最短路径。
        int k = 0;
        for (int i = 1; i < vexs.length; i++) {
            // 寻找当前最小的路径；
            // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
            int min = MA;
            for (int j = 0; j < vexs.length; j++) {
                if (flag[j] == false && dist[j] < min) {
                    min = dist[j];
                    k = j;
                }
            }
            // 标记"顶点k"为已经获取到最短路径
            flag[k] = true;

            // 修正当前最短路径和前驱顶点
            // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
            for (int j = 0; j < vexs.length; j++) {
                int tmp = (arc[k][j] == MA ? MA : (min + arc[k][j]));
                if (flag[j] == false && (tmp < dist[j])) {
                    dist[j] = tmp;
                    prev[j] = k;
                }
            }
        }

        // 打印dijkstra最短路径的结果
        for (int i = 0; i < vexs.length; i++)
            System.out.println("  shortest(" + vexs[vs] + ", " + vexs[i] + ")=" + dist[i]);
    }

    /**
     * 获取以f节点开始的路径的终点
     *
     * @param parent
     * @param f
     * @return
     */
    private int find(int[] parent, int f) {
        while (parent[f] > 0) {
            f = parent[f];
        }
        return f;
    }

    /**
     * 获取边集数组
     *
     * @return
     */
    private Edge[] getEdges() {
        Edge[] edges = new Edge[numEdges];
        int k = 0;
        for (int i = 0; i < numVertexes; i++) {
            for (int j = i; j < numVertexes; j++) {
                if (arc[i][j] > 0 && arc[i][j] < MA) {
                    edges[k++] = new Edge(i, j, arc[i][j]);
                }
            }
        }
        return edges;
    }


    public String[] getVexs() {
        return vexs;
    }

    public void setVexs(String[] vexs) {
        this.vexs = vexs;
    }

    public int[][] getArc() {
        return arc;
    }

    public void setArc(int[][] arc) {
        this.arc = arc;
    }

}
